// 以最大堆为例：
// 1、首先构建一个大顶堆序列（存入数组中）
// 2、将堆顶元素和最后一个元素交换，使末尾存入最大值
// 3、将剩余的n-1个元素重新构建成一个大顶堆，重复上面操作

//堆排序函数
function heapSort(arr){
  for(let i=parseInt(arr.length/2)-1;i>=0;i--){
    adjustHeap(arr,i,arr.length)
  }

}

// 调整函数
// arr 待排序的数组
// i 表示等待调整的那个非叶子节点的索引
// length 待调整的长度
function adjustHeap(arr,i,length){
  var notLeafNode = arr[i] //非叶子节点的值
  for(var k=i*2+1;k<length;k=k*2+1){
    if(k+1<length && arr[k]<arr[k+1]){
      k++
    }
    if(arr[k]>notLeafNode){
      将当前节点赋值为
      arr[i] = arr[k]
      i = k
    }else{
      break
    }
  }
  // 循环结束后,将i索引处的节点赋值为之前存的那个非叶子节点的值
  arr[i] = notLeafNode
}